package com.leetcode.algorithm.y22.m07;

import java.util.ArrayList;
import java.util.List;

/**
 * 438. 找到字符串中所有字母异位词
 * 
 * https://leetcode.cn/problems/find-all-anagrams-in-a-string/
 * 
 * @author jie.deng
 *
 */
class Question0438Solution01 {
	
	public List<Integer> findAnagrams(String s, String p) {
		List<Integer> list = new ArrayList<>();
		int lenS = s.length();
		int lenP = p.length();
		if (lenP > lenS) {
			return list;
		}
		int[] cntS = new int[26];
		int[] cntP = new int[26];
		for (int i = 0; i < lenP; i++) {
			cntS[s.charAt(i) - 'a']++;
			cntP[p.charAt(i) - 'a']++;
		}
		int diffCnt = 0;
		for (int i = 0; i < 26; i++) {
			if (cntP[i] != cntS[i]) {
				diffCnt++;
			}
		}
		if (diffCnt == 0) {
			list.add(0);
		}
		for (int i = 1; i + lenP - 1 < lenS; i++) {
			// 滑动窗口向右移动，减去了最前面的一个字符，增加了最后面的一个字符，对于diffCnt可能的影响
			int idxL = s.charAt(i - 1) - 'a';
			int idxR = s.charAt(i + lenP - 1) - 'a';
			if (idxL == idxR) {
				// diffCnt不变
				if (diffCnt == 0) {
					list.add(i);
				}
				continue;
			}
			if (cntP[idxL] == cntS[idxL]) {
				diffCnt++;
			} else if (cntS[idxL] == cntP[idxL] + 1) {
				diffCnt--;
			}
			cntS[idxL]--;

			if (cntP[idxR] == cntS[idxR]) {
				diffCnt++;
			} else if (cntS[idxR] == cntP[idxR] - 1) {
				diffCnt--;
			}
			cntS[idxR]++;

			if (diffCnt == 0) {
				list.add(i);
			}
		}
		return list;
	}
    
}